package org.zhangyp.n03algorithm.n02Rec;

import java.util.List;

/**
 * 递归思想-斐波那契数列
 */
public class Fibonacci {
    public static int fab(int n) {
        if (n <= 2) {
            return 1;
        }
        return fab(n - 1) + fab(n - 2);
    }

    public static int[] noFab(int n) {
        int[] data = new int[n];
        data[0] = 1;
        if (n > 1) {
            data[1] = 1;
        }
        if (n > 2) {
            for (int i = 2; i < n; i++) {
                data[i] = data[i - 1] + data[i - 2];
            }
        }
        return data;
    }

    public static int tailFab(int n, int pre1, int pre2) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return pre1 + pre2;
        }
        return tailFab(n - 1, pre1 + pre2, pre1);
    }


    public static void fab2(int n, List<Integer> list) {
        if (n == 2) {
            fab2(n - 1, list);
            list.add(1);
        } else if (n < 2) {
            list.add(1);
        } else {
            fab2(n - 1, list);
            list.add(list.get(n - 1 - 1) + list.get(n - 1 - 2));
        }
    }


    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        return tailFab(n, 3, 2, 1);
    }

    public static int tailFab(int n, int i, int pre1, int pre2) {
        if (i == n) {
            return pre1 + pre2;
        }
        return tailFab(n, i + 1, pre1 + pre2, pre1);
    }

    public static void main(String[] args) {
        /*List<Integer> list = new ArrayList<>();
        fab2(50,list);
        System.out.println(list);*/


        /*for (int i = 1; i <= 50; i++) {
            System.out.print(tailFab(i, 1, 1) + ",");
        }*/
        for (int i = 1; i <= 50; i++) {
            long start = System.currentTimeMillis();
            int[] ints = noFab(i);
            /*for(int n:ints){
                System.out.print(n + ",");
            }*/
            System.out.println("耗时：" + (System.currentTimeMillis() - start) + "ms");
        }
    }
}
